package com.LatitudeYao;

import java.util.Arrays;

/**
 * Created by GTS on 2017/8/14.
 */
public class QuickSortYM {
    public static int getMiddle(int[] list,int low,int high){
        int temp = list[low];//首元素默认为枢轴
        while(low < high) {//整体执行循环，从左向右扫描
            while (low < high && list[high] > temp) {//=从右向左扫描，如果元素大于temp则不交换，直接移动游标
                high--;
            }
            list[low] = list[high];//执行交换

            while (low < high && list[low] < temp) {//从左向右，如果list[low] < temp ,直接移动游标
                low++;
            }
            list[high] = list[low];//赋值回去
        }
        list[low] = temp;//
        return low;//返回枢轴元素，这个地方就是
    }
    public static void quickSort(int[] list, int low, int high){
        if(low < high){
            int middle = getMiddle(list, low, high);
            quickSort(list,low,middle-1);
            quickSort(list,middle+1,high);
        }
    }
    public static void main(String[] args) {
        int[] intArray = {1,2,3,4,5,12,11,13,9,8,7,6};
        System.out.println("Before QuickSort ");
        for (int i = 0; i <intArray.length ; i++) {
            System.out.println(intArray[i]);
        }
        System.out.println("After QuickSort ");
        quickSort(intArray,0,intArray.length-1);
        for (int i = 0; i <intArray.length ; i++) {
            System.out.println(intArray[i]);
        }

    }
}
